Best problems of Dynamic Programming to Practice ?

LeetCode Best Dynamic Programming Problems for Practice ? 

 ▶  Climbing Stairs

Answer : 👇

class Solution
{
public:
    int dp[50] = {0};
    int climbStairs(int n)
    {

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; ++i)
        {
            dp[i] = dp[i - 2] + dp[i - 1];
        }

        return dp[n];
    }
};

▶  Best Time to Buy and Sell Stock

 Answer : 👇

class Solution
{
    int dp[100005][2]; // for memoizations
    int n;
    int find(vector<int> &v, int i, bool buy, int k)
    {
        if (n == 1 || i == n || k == 0)
            return 0;
        if (dp[i][buy] != -1)
            return dp[i][buy];
        if (buy)
        {

            return dp[i][buy] = max(-v[i] + find(v, i + 1, !buy, k), find(v, i + 1, buy, k));
        }
        else
        {

            return dp[i][buy] = max(v[i], find(v, i + 1, buy, k));
        }
    }

public:
    int maxProfit(vector<int> &prices)
    {
        n = prices.size();
        memset(dp, -1, sizeof(dp));
        return max(0, find(prices, 0, 1, 1));
    }

▶  Best Time to Buy and Sell Stock II

/*-----------------RECURSIVE CODE 👇  -------------------------*/
class Solution
{
    int n;
    int dp[30005][2];
    int find(vector<int> &v, int i, bool buy)
    {
        if (n == 1 || i == n)
            return 0;

        if (dp[i][buy] != -1)
            return dp[i][buy];
        if (buy)
        {
            return dp[i][buy] = max((find(v, i + 1, !buy) - v[i]), find(v, i + 1, buy));
        }
        else
        {
            return dp[i][buy] = max(v[i] + find(v, i + 1, !buy), find(v, i + 1, buy));
        }
    }

public:
    int maxProfit(vector<int> &prices)
    {

        n = prices.size();
        memset(dp, -1, sizeof(dp));
        return max(find(prices, 0, 1), 0);
    }
};

/*-----------------Top Down DP 👇 -------------------------*/

▶ Best Time to Buy and Sell Stock III

/*-----------------RECURSIVE CODE 👇  -------------------------*/
class Solution
{
    int n;
    //  for  dp[N][buy][k]
    int dp[100001][2][3];
    int find(vector<int> &v, int i, bool buy, int k)
    {
        if (n == 1 || i == n || k == 0)
            return 0;

        if (dp[i][buy][k] != -1)
            return dp[i][buy][k];
        if (buy)
        {
            return dp[i][buy][k] = max(find(v, i + 1, !buy, k) - v[i], find(v, i + 1, buy, k));
        }
        else
        {
            return dp[i][buy][k] = max(v[i] + find(v, i + 1, !buy, k - 1), find(v, i + 1, buy, k));
        }
    }

public:
    int maxProfit(vector<int> &prices)
    {

        n = prices.size();
        memset(dp, -1, sizeof(dp));
        return find(prices, 0, 1, 2);
    }
};
/*-----------------Top Down DP 👇 -------------------------*/

Category: Python | General Programming

Relavent Tags: Dynamic Programming